#include "CLineSegment2d.h"



CSpace::Relativity CLineSegment2d::DetermineSpace( const CVector2d& v0, const CVector2d& v1,
												   const CVector2d& point )
{
	fixed rel = CMathFixed::Mul( point.m_j - v0.m_j, v1.m_i - v0.m_i ) - 
				CMathFixed::Mul( point.m_i - v0.m_i, v1.m_j - v0.m_j );

	if( rel < 0 )
		return CSpace::Inside;
	else
	if( rel > 0 )
		return CSpace::Outside;
	else
		return CSpace::Intersecting;
}



fixed CLineSegment2d::ClosestPoint( const CVector2d& v0, const CVector2d& v1,
									const CVector2d& point, CVector2d& closestPoint )
{
	CVector2d v0v1 = v1 - v0;
	fixed u = ( point - v0 ) * v0v1; 

	if( u > 0 )
	{
		fixed d = v0v1 * v0v1;

		if( u < d )
		{
			u = CMathFixed::Div( u, d );
			closestPoint = v0 + u * v0v1;
		}
		else
		{
			u = CMathFixed::One;
			closestPoint = v1;
		}
	}
	else
	{
		u = 0;
		closestPoint = v0;
	}

	return u;
}


CVector2d& CLineSegment2d::ShortestVectorToPoint( const CVector2d& v0, const CVector2d& v1,
												  const CVector2d& point, 
												  CVector2d& v, fixed& u )
{
	u = ClosestPoint( v0, v1, point, v );
	v = point - v;

	return v;
}


void CLineSegment2d::ShortestVectorToSegment( const CVector2d& seg0V0, const CVector2d& seg0V1,
					 								const CVector2d& seg1V0, const CVector2d& seg1V1,
													CVector2d& c1, CVector2d& c2, fixed* u0, fixed *u1 )
{
	fixed EPSILON = CMathFixed_FloatToFixed( 0.001f );
	
	CVector2d   d1 = seg0V1 - seg0V0;
	CVector2d   d2 = seg1V1 - seg1V0;
	CVector2d   r = seg0V0 - seg1V0;

	fixed a = d1 * d1;
	fixed e = d2 * d2;
	fixed f = d2 * r;

	fixed &s = *u0;
	fixed &t = *u1;

	// check if both segments degenerate into points

	if ( a <= EPSILON && e <= EPSILON )
	{
		c1 = seg0V0;
		c2 = seg1V0;
		s = t = 0;
		return;
	}

	if ( a <= EPSILON )
	{
		// first segment degenrates into a point
		s = 0;
		t = CMathFixed::Div( f, e );
		t = CMathFixed::Clamp( t, 0, CMathFixed::One );
	}
	else
	{
		fixed c = d1 * r;
		if ( e <= EPSILON )
		{
			t = 0;
			s = CMathFixed::Clamp( CMathFixed::Div( -c, a ), 0, CMathFixed::One );
		}
		else
		{
			// the general non-degenrate case
			fixed b = d1 * d2;
			fixed denom = CMathFixed::Mul( a, e ) - CMathFixed::Mul( b, b );

			// if segments are not parallel, compute closest point on L1 to L2 and
			// clamp to segment s1, else pick arbitrary s

			if ( CMathFixed::Abs( denom ) > EPSILON )
			{
				s = CMathFixed::Clamp( CMathFixed::Div( CMathFixed::Mul( b,f ) - CMathFixed::Mul( c, e ), denom ), 0, CMathFixed::One );
			}
			else
				s = 0;

			fixed tNom = CMathFixed::Mul( b, s ) + f;

			if ( tNom < 0 )
			{
				t = 0;
				s = CMathFixed::Clamp( CMathFixed::Div( -c, a ), 0, CMathFixed::One );
			}
			else if ( tNom > e )
			{
				t = 1;
				s = CMathFixed::Clamp( CMathFixed::Div( b - c, a ), 0, CMathFixed::One );
			}
			else
				t = CMathFixed::Div( tNom, e );
		}
	}

	c1 = seg0V0 + d1 * s;
	c2 = seg1V0 + d2 * t;

}


void CLineSegment2d::ComputeVertexNormal( const CVector2d& vtx0, const CVector2d& vtx1,
										  const CVector2d& vtx2,
										  CVector2d& vtxNormal, 
										  CSpace::Relativity relativity )
{
	ASSERT( relativity == CSpace::Inside || relativity == CSpace::Outside );

	CVector2d s1 = vtx2 - vtx1;

	vtxNormal = vtx0 - vtx1;
	vtxNormal = vtxNormal + s1;
	vtxNormal.m_i >>= 1;
	vtxNormal.m_j >>= 1;
	
	if( relativity == CSpace::Inside )
		vtxNormal -= vtx1;
	else
		vtxNormal = vtx1 - vtxNormal;

	vtxNormal.Normalize();
}


/*
 *	Here's the way this works ( from comp.graphics.algoriths FAQ ):
 *  ----------------------------------------------------------------------
 *  Subject 1.03: How do I find intersections of 2 2D line segments?
 *  
 *  This problem can be extremely easy or extremely difficult; it
 *  depends on your application. If all you want is the intersection
 *  point, the following should work:
 *
 *  Let A,B,C,D be 2-space position vectors.  Then the directed line
 *  segments AB & CD are given by:
 *
 *      AB=A+r(B-A), r in [0,1]
 *      CD=C+s(D-C), s in [0,1]
 *
 *  If AB & CD intersect, then
 *
 *      A+r(B-A)=C+s(D-C), or
 *
 *      Ax+r(Bx-Ax)=Cx+s(Dx-Cx)
 *      Ay+r(By-Ay)=Cy+s(Dy-Cy)  for some r,s in [0,1]
 *
 *  Solving the above for r and s yields
 *
 *          (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
 *      r = -----------------------------  (eqn 1)
 *          (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
 *
 *          (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
 *      s = -----------------------------  (eqn 2)
 *          (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
 *
 *  Let P be the position vector of the intersection point, then
 *
 *      P=A+r(B-A) or
 *
 *      Px=Ax+r(Bx-Ax)
 *      Py=Ay+r(By-Ay)
 *
 *  By examining the values of r & s, you can also determine some
 *  other limiting conditions:
 *
 *      If 0<=r<=1 & 0<=s<=1, intersection exists
 *         r<0 or r>1 or s<0 or s>1 line segments do not intersect
 *
 *      If the denominator in eqn 1 is zero, AB & CD are parallel
 *      If the numerator in eqn 1 is also zero, AB & CD are collinear.
 *
 *  If they are collinear, then the segments may be projected to the x- 
 *  or y-axis, and overlap of the projected intervals checked.
 *
 *  If the intersection point of the 2 lines are needed (lines in this
 *  context mean infinite lines) regardless whether the two line
 *  segments intersect, then
 *
 *      If r>1, P is located on extension of AB
 *      If r<0, P is located on extension of BA
 *      If s>1, P is located on extension of CD
 *      If s<0, P is located on extension of DC
 *
 *  Also note that the denominators of eqn 1 & 2 are identical.
 *
 *  References:
 *
 *  [O'Rourke (C)] pp. 249-51
 *  [Gems III] pp. 199-202 "Faster Line Segment Intersection,"
*/
boolean	CLineSegment2d::Intersects( const CVector2d& seg0V0, const CVector2d& seg0V1,
									const CVector2d& seg1V0, const CVector2d& seg1V1,
									fixed* u0, fixed *u1 )
{
	boolean intersects = FALSE;

	CVector2d d1 = seg0V1 - seg0V0;
	CVector2d d2 = seg1V1 - seg1V0;

	fixed denom = CMathFixed::Mul( d1.m_i, d2.m_j ) - CMathFixed::Mul( d1.m_j, d2.m_i );

	if( denom )
	{ 
		CVector2d delta = seg1V0 - seg0V0;

		*u0 = CMathFixed::Div( CMathFixed::Mul( delta.m_i, d2.m_j ) - 
							   CMathFixed::Mul( delta.m_j, d2.m_i ), denom );
		*u1 = CMathFixed::Div( CMathFixed::Mul( delta.m_i, d1.m_j ) - 
							   CMathFixed::Mul( delta.m_j, d1.m_i ), denom );

		intersects = TRUE;
	}

	return intersects;
}


void CLineSegment2d::ExtractSuccessiveVertices( CVector2d* vtx, int32 nOfVerticesInClosedGraph, 
												int32 idxOfFirst, 
												CVector2d** v0, CVector2d** v1, CVector2d** v2 )
{ 
	ASSERT( v0 && v1 );

	if( v2 )
		*v2 = NULL;

	*v0 = &vtx[ idxOfFirst ];
									
	if( idxOfFirst == nOfVerticesInClosedGraph - 1 )
		*v1 = &vtx[0];
	else
	{
		*v1 = *v0 + 1;
		
		if( v2 && idxOfFirst == nOfVerticesInClosedGraph - 2 )
			*v2 = &vtx[0];
	}

	if( v2 && !( *v2 ) )
		*v2 = *v1 + 1;
}
